{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Matrix Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxMatrixSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大方阵和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个&nbsp;<code>n x n</code>&nbsp;的整数方阵&nbsp;<code>matrix</code>&nbsp;。你可以执行以下操作&nbsp;<strong>任意次</strong>&nbsp;：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择&nbsp;<code>matrix</code>&nbsp;中&nbsp;<strong>相邻</strong>&nbsp;两个元素，并将它们都 <strong>乘以</strong>&nbsp;<code>-1</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果两个元素有 <strong>公共边</strong>&nbsp;，那么它们就是 <strong>相邻</strong>&nbsp;的。</p>\n",
    "\n",
    "<p>你的目的是 <strong>最大化</strong>&nbsp;方阵元素的和。请你在执行以上操作之后，返回方阵的&nbsp;<strong>最大</strong>&nbsp;和。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/07/16/pc79-q2ex1.png\" style=\"width: 401px; height: 81px;\">\n",
    "<pre><b>输入：</b>matrix = [[1,-1],[-1,1]]\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>我们可以执行以下操作使和等于 4 ：\n",
    "- 将第一行的 2 个元素乘以 -1 。\n",
    "- 将第一列的 2 个元素乘以 -1 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/07/16/pc79-q2ex2.png\" style=\"width: 321px; height: 121px;\">\n",
    "<pre><b>输入：</b>matrix = [[1,2,3],[-1,-2,-3],[1,2,3]]\n",
    "<b>输出：</b>16\n",
    "<b>解释：</b>我们可以执行以下操作使和等于 16 ：\n",
    "- 将第二行的最后 2 个元素乘以 -1 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == matrix.length == matrix[i].length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 250</code></li>\n",
    "\t<li><code>-10<sup>5</sup> &lt;= matrix[i][j] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-matrix-sum](https://leetcode.cn/problems/maximum-matrix-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-matrix-sum](https://leetcode.cn/problems/maximum-matrix-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,-1],[-1,1]]', '[[1,2,3],[-1,-2,-3],[1,2,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        # 分别看负数有多少,以及距离0最近的负数\n",
    "        sum_ = 0\n",
    "        negative_cnt = 0\n",
    "        negative_closest_to_zeo = None\n",
    "        non_negative_closest_to_zeo = None\n",
    "        n = len(matrix[0])\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                sum_ += abs(matrix[i][j])\n",
    "                if matrix[i][j] < 0:\n",
    "                    negative_cnt += 1\n",
    "                    if negative_closest_to_zeo is not None:\n",
    "                        negative_closest_to_zeo = max(negative_closest_to_zeo, matrix[i][j])\n",
    "                    else:\n",
    "                        negative_closest_to_zeo = matrix[i][j]\n",
    "\n",
    "                else:\n",
    "                    if non_negative_closest_to_zeo is not None:\n",
    "                        non_negative_closest_to_zeo = min(non_negative_closest_to_zeo, matrix[i][j])\n",
    "                    else:\n",
    "                        non_negative_closest_to_zeo = matrix[i][j]\n",
    "\n",
    "        # 分三种情况\n",
    "        if negative_cnt % 2 == 0:\n",
    "            return sum_\n",
    "        elif non_negative_closest_to_zeo is None or abs(negative_closest_to_zeo) < non_negative_closest_to_zeo:\n",
    "            return sum_ + 2 * negative_closest_to_zeo\n",
    "        else:\n",
    "            return sum_ - 2 * non_negative_closest_to_zeo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        cnt, total = 0, 0\n",
    "        min_element = 100001\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                ele = matrix[i][j]\n",
    "                min_element = min(abs(ele), min_element)\n",
    "                if ele < 0:\n",
    "                    cnt += 1\n",
    "                total += abs(ele)\n",
    "        if cnt % 2 == 0:\n",
    "            return total\n",
    "        return total - 2 * min_element"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "\n",
    "        zero = False\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        negcnt = 0\n",
    "        min_number = float(\"inf\")\n",
    "        total = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 0:\n",
    "                    zero = True\n",
    "                elif matrix[i][j] < 0:\n",
    "                    negcnt += 1\n",
    "                total += abs(matrix[i][j])\n",
    "                min_number = min(abs(matrix[i][j]), min_number)\n",
    "        if negcnt % 2 == 1 and zero is False:\n",
    "            total -= 2*min_number\n",
    "\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        # 一定是可以化简到只有一个负数的\n",
    "        s = cnt = 0\n",
    "        minval = inf\n",
    "        n = len(matrix)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                x = matrix[i][j]\n",
    "                if x < 0:\n",
    "                    cnt += 1\n",
    "                s += abs(x)\n",
    "                minval = min(minval, abs(x))\n",
    "        if cnt & 1:\n",
    "            s -= 2 * minval\n",
    "         \n",
    "        return s\n",
    "                \n",
    "\n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        cnt, tot = 0, 0\n",
    "        mx, n = sys.maxsize, len(matrix)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                mx = min(mx, abs(matrix[i][j]))\n",
    "                if matrix[i][j] < 0:\n",
    "                    cnt += 1\n",
    "                tot += abs(matrix[i][j])\n",
    "        if cnt % 2 == 0:\n",
    "            return tot\n",
    "        return tot - 2 * mx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        Sum = 0  #各个数字的绝对值相加\n",
    "        count = 0 #负数的个数\n",
    "        Min = float('inf')  #绝对值最小的数\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j] < 0:\n",
    "                    count += 1\n",
    "                Min = min(abs(Min), abs(matrix[i][j]))\n",
    "                Sum += abs(matrix[i][j])\n",
    "        return Sum if count % 2 == 0 else Sum - 2 * Min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        cnt = 0\n",
    "        ans = 0\n",
    "        x = 1e10\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j] <= 0:\n",
    "                    ans -= matrix[i][j]\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    ans += matrix[i][j]\n",
    "                x = min(x,abs(matrix[i][j]))\n",
    "        return ans - 2*x*(cnt%2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        neg_count = 0  # 记录负数个数\n",
    "        abs_sum = 0    # 记录所有元素的绝对值和\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                num = matrix[i][j]\n",
    "                abs_sum += abs(num)\n",
    "                if num < 0:\n",
    "                    neg_count += 1\n",
    "\n",
    "        # 如果负数个数为偶数，则全部变成正数\n",
    "        if neg_count % 2 == 0:\n",
    "            return abs_sum\n",
    "        else:\n",
    "            # 如果负数个数为奇数，则将绝对值最小的一个负数变成正数\n",
    "            min_abs = float('inf')\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if abs(matrix[i][j]) < min_abs:\n",
    "                        min_abs = abs(matrix[i][j])\n",
    "\n",
    "            return abs_sum - 2 * min_abs\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        cnt = 0   # 负数元素的数量\n",
    "        total = 0   # 所有元素的绝对值之和\n",
    "        mn = float(\"INF\")   # 方阵元素的最小绝对值\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                mn = min(mn, abs(matrix[i][j]))\n",
    "                if matrix[i][j] < 0:\n",
    "                    cnt += 1\n",
    "                total += abs(matrix[i][j])\n",
    "        # 按照负数元素的数量的奇偶性讨论\n",
    "        if cnt % 2 == 0:\n",
    "            return total\n",
    "        else:\n",
    "            return total - 2 * mn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        minN = inf\n",
    "        minus = ans = 0\n",
    "        for x in matrix:\n",
    "            for y in x:\n",
    "                if y < 0:\n",
    "                    y = -y\n",
    "                    minus ^= 1\n",
    "                if y < minN:\n",
    "                    minN = y\n",
    "                ans += y\n",
    "        return ans - 2 * minus * minN"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "         # 初始化负数计数器\n",
    "        negative_count = 0\n",
    "\n",
    "        # 遍历二维列表\n",
    "        for row in matrix:\n",
    "            for num in row:\n",
    "                if num < 0:\n",
    "                    negative_count += 1\n",
    "\n",
    "        min_absolute_value = float('inf')\n",
    "\n",
    "        absolute_value_sum = 0\n",
    "\n",
    "        # 遍历二维列表\n",
    "        for row in matrix:\n",
    "            for num in row:\n",
    "                # 计算当前元素的绝对值\n",
    "                absolute_value = abs(num)\n",
    "                absolute_value_sum += abs(num)\n",
    "                # 更新绝对值的最小值\n",
    "                if absolute_value < min_absolute_value:\n",
    "                    min_absolute_value = absolute_value\n",
    "        if negative_count % 2 == 1:\n",
    "            answer = absolute_value_sum - 2*min_absolute_value\n",
    "        else :\n",
    "            answer = absolute_value_sum\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        s=0\n",
    "        mm=10**5\n",
    "        flag=True\n",
    "        for row in matrix:\n",
    "            for c in row:\n",
    "                s+=abs(c)\n",
    "                mm=min(mm,abs(c))\n",
    "                if c<0:\n",
    "                    flag = not flag\n",
    "        if flag:\n",
    "            return s\n",
    "        return s-mm-mm\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        cnt = 0\n",
    "        ans = 0\n",
    "        x = 1e10\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j] <= 0:\n",
    "                    ans -= matrix[i][j]\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    ans += matrix[i][j]\n",
    "                x = min(x,abs(matrix[i][j]))\n",
    "        if cnt%2 == 0:\n",
    "            return ans\n",
    "        else:\n",
    "            return ans - 2*x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        counts = 0\n",
    "        min_num = inf\n",
    "        res = 0\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j]<0:\n",
    "                    counts += 1\n",
    "                x = abs(matrix[i][j])\n",
    "                res += x\n",
    "                min_num = min(min_num,x)\n",
    "        if counts%2==1:\n",
    "            res -= min_num*2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        Sum = 0  #各个数字的绝对值相加\n",
    "        count = 0 #负数的个数\n",
    "        Min = float('inf')  #绝对值最小的数\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j] < 0:\n",
    "                    count += 1\n",
    "                Min = min(abs(Min), abs(matrix[i][j]))\n",
    "                Sum += abs(matrix[i][j])\n",
    "        return Sum if count % 2 == 0 else Sum - 2 * Min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        # 分别看负数有多少,以及距离0最近的负数\n",
    "        sum_ = 0\n",
    "        negative_cnt = 0\n",
    "        negative_closest_to_zeo = -99999999999\n",
    "        non_negative_closest_to_zeo = 99999999999\n",
    "        n = len(matrix[0])\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                sum_ += abs(matrix[i][j])\n",
    "                if matrix[i][j] < 0:\n",
    "                    negative_cnt += 1\n",
    "                    negative_closest_to_zeo = max(negative_closest_to_zeo, matrix[i][j])\n",
    "                else:\n",
    "                    non_negative_closest_to_zeo = min(non_negative_closest_to_zeo, matrix[i][j])\n",
    "\n",
    "\n",
    "        # 分三种情况\n",
    "        if negative_cnt % 2 == 0:\n",
    "            return sum_\n",
    "        elif abs(negative_closest_to_zeo) < non_negative_closest_to_zeo:\n",
    "            return sum_ + 2 * negative_closest_to_zeo\n",
    "        else:\n",
    "            return sum_ - 2 * non_negative_closest_to_zeo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        # 一定是可以化简到只有一个负数的\n",
    "        s = cnt = 0\n",
    "        minval = inf\n",
    "        n = len(matrix)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                x = matrix[i][j]\n",
    "                if x < 0:\n",
    "                    cnt += 1\n",
    "                s += abs(x)\n",
    "                minval = min(minval, abs(x))\n",
    "        if cnt & 1:\n",
    "            s -= 2 * minval\n",
    "         \n",
    "        return s\n",
    "                \n",
    "\n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # * 贪心\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        cnt = 0   # 负数元素的数量\n",
    "        total = 0   # 所有元素的绝对值之和\n",
    "        mn = float(\"INF\")   # 方阵元素的最小绝对值\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                mn = min(mn, abs(matrix[i][j]))\n",
    "                if matrix[i][j] < 0:\n",
    "                    cnt += 1\n",
    "\n",
    "                total += abs(matrix[i][j])\n",
    "\n",
    "        # 按照负数元素的数量的奇偶性讨论\n",
    "        if cnt % 2 == 0:\n",
    "            return total\n",
    "        else:\n",
    "            return total - 2 * mn\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        cnt = tot = 0\n",
    "        mx = 10 ** 5\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                mx = min(mx, abs(matrix[i][j]))\n",
    "                if matrix[i][j] < 0:\n",
    "                    cnt += 1\n",
    "                tot += abs(matrix[i][j])\n",
    "        return tot - 2 * mx if cnt & 1 else tot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        cnt = 0\n",
    "        mi = 100001\n",
    "        s = 0\n",
    "        for line in matrix:\n",
    "            for num in line:\n",
    "                if abs(num) < mi:\n",
    "                    mi = abs(num)\n",
    "                if num < 0:\n",
    "                    cnt += 1\n",
    "                    s -= num\n",
    "                else:\n",
    "                    s += num\n",
    "\n",
    "        if cnt % 2 == 1:\n",
    "            s -= mi + mi\n",
    "        \n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        dix = 100000 # 记录绝对值最小的数\n",
    "        cnt_neg = 0  # 记录负数的个数\n",
    "        res = 0\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                res += abs(matrix[i][j])\n",
    "                dix = min(dix, abs(matrix[i][j]))\n",
    "                if matrix[i][j]<=0:\n",
    "                    cnt_neg += 1\n",
    "            \n",
    "        if cnt_neg%2==0:\n",
    "            return res\n",
    "        else:\n",
    "            return res-2*dix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        cnt = 0   # 负数元素的数量\n",
    "        total = 0   # 所有元素的绝对值之和\n",
    "        mn = float(\"INF\")   # 方阵元素的最小绝对值\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                mn = min(mn, abs(matrix[i][j]))\n",
    "                if matrix[i][j] < 0:\n",
    "                    cnt += 1\n",
    "                total += abs(matrix[i][j])\n",
    "        # 按照负数元素的数量的奇偶性讨论\n",
    "        if cnt % 2 == 0:\n",
    "            return total\n",
    "        else:\n",
    "            return total - 2 * mn\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        negative_cnt = 0\n",
    "        abs_sum = 0\n",
    "        abs_min = float(\"inf\")\n",
    "        for row in matrix:\n",
    "            for col in row:\n",
    "                if col < 0:\n",
    "                    negative_cnt += 1\n",
    "                    col = -col\n",
    "                abs_sum += col\n",
    "                abs_min = col if col < abs_min else abs_min\n",
    "        if negative_cnt % 2:\n",
    "            return abs_sum - 2 * abs_min\n",
    "        else:\n",
    "            return abs_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        neg = False\n",
    "        mn = inf   # 绝对值最小的数\n",
    "        for n in chain.from_iterable(matrix):\n",
    "            if (a := abs(n)) < mn:\n",
    "                mn = a\n",
    "            ans += a\n",
    "            if n <= 0:\n",
    "                neg = not neg\n",
    "        if neg:\n",
    "            ans -= mn << 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        cnt =sum(x < 0 for row in matrix for x in row )\n",
    "        all = sum(abs(x) for row in matrix for x in row)\n",
    "        \n",
    "        minv = min(abs(x) for row in matrix for x in row)\n",
    "\n",
    "        return all if cnt%2==0 else all-2*minv\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        zero = False\n",
    "        negative = False\n",
    "        for i in range(n):\n",
    "            if zero:\n",
    "                break\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 0:\n",
    "                    zero = True\n",
    "                    break\n",
    "        ans = 0 \n",
    "        if zero:\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    ans += abs(matrix[i][j])\n",
    "            return ans\n",
    "        else:\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if matrix[i][j] < 0:\n",
    "                        negative = not negative\n",
    "            if not negative:\n",
    "                for i in range(n):\n",
    "                    for j in range(n):\n",
    "                        ans += abs(matrix[i][j])\n",
    "                        \n",
    "                return ans\n",
    "            else:\n",
    "                mi = 10**5\n",
    "                for i in range(n):\n",
    "                    for j in range(n):\n",
    "                        ans += abs(matrix[i][j])\n",
    "                        mi = min(mi,abs(matrix[i][j]))\n",
    "                return ans - mi*2\n",
    "\n",
    "        \n",
    "            \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        neg = False\n",
    "        mn = inf   # 绝对值最小的数\n",
    "        for n in chain.from_iterable(matrix):\n",
    "            ans += abs(n)\n",
    "            if abs(n) < mn:\n",
    "                mn = abs(n)\n",
    "            if n <= 0:\n",
    "                neg = not neg\n",
    "        if neg:\n",
    "            ans -= mn << 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        total_sum = 0  # 记录矩阵所有元素的和\n",
    "        min_abs_val = float('inf')  # 记录矩阵中绝对值最小的元素\n",
    "        num_negatives = 0  # 记录矩阵中负数的个数\n",
    "\n",
    "        for row in matrix:\n",
    "            for num in row:\n",
    "                total_sum += abs(num)  # 累加元素的绝对值\n",
    "                min_abs_val = min(min_abs_val, abs(num))  # 更新绝对值最小的元素\n",
    "                if num < 0:\n",
    "                    num_negatives += 1  # 计算负数的个数\n",
    "\n",
    "        # 如果负数的个数是偶数，则所有数都可以变为正数\n",
    "        if num_negatives % 2 == 0:\n",
    "            return total_sum\n",
    "        else:\n",
    "            # 如果负数的个数是奇数，则结果应减去绝对值最小的元素的两倍（即将其变为负数）\n",
    "            return total_sum - 2 * min_abs_val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        neg = False\n",
    "        mn = inf   # 绝对值最小的数\n",
    "        for n in chain.from_iterable(matrix):\n",
    "            if (a := abs(n)) < mn:\n",
    "                mn = a\n",
    "            ans += a\n",
    "            if n <= 0:\n",
    "                neg = not neg\n",
    "        if neg:\n",
    "            ans -= mn << 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        n = len(matrix)\n",
    "        tmp = []\n",
    "        min = float(\"inf\")\n",
    "        for i in range(0, n):\n",
    "            for j in range(0, n):\n",
    "                if abs(matrix[i][j]) < min:\n",
    "                    min = abs(matrix[i][j])\n",
    "                ans += abs(matrix[i][j])\n",
    "                if matrix[i][j] < 0:\n",
    "                    tmp.append(matrix[i][j])\n",
    "                    matrix[i][j] = -matrix[i][j]\n",
    "        if len(tmp) % 2 == 1:\n",
    "            ans -= 2*min\n",
    "        return ans\n",
    "        \n",
    "            \n",
    "                \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        r, c = len(matrix), len(matrix[0])\n",
    "        pos = []\n",
    "        neg = []\n",
    "        zero = []\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if matrix[i][j] > 0:\n",
    "                    pos.append(matrix[i][j])\n",
    "                elif matrix[i][j] < 0:\n",
    "                    neg.append(matrix[i][j])\n",
    "                else:\n",
    "                    zero.append(0)\n",
    "\n",
    "        if len(neg) % 2 == 0:\n",
    "            return sum(pos) - sum(neg)\n",
    "        else:\n",
    "            if len(zero) > 0:\n",
    "                return sum(pos) - sum(neg)\n",
    "            else:\n",
    "                if len(pos) > 0:\n",
    "                    min_ = min(pos) \n",
    "                    max_ = max(neg)\n",
    "                    if min_ > -max_:\n",
    "                        return sum(pos) - sum(neg) + 2*max_\n",
    "                    else:\n",
    "                        return -sum(neg) + sum(pos) - 2*min_\n",
    "                else:\n",
    "                    max_ = max(neg)\n",
    "                    return -sum(neg) + 2 * max_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        s = sum(sum(row) for row in matrix)\n",
    "        neg = [x for row in matrix for x in row if x <= 0]\n",
    "        if len(neg) % 2 == 0:\n",
    "            return s - sum(neg) * 2\n",
    "        return s - sum(neg) * 2 - min([abs(x) for row in matrix for x in row]) * 2\n",
    "        \n",
    "            \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 8 directions\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        st = []\n",
    "        n = len(matrix)\n",
    "        ret, mn = 0, inf\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] < 0:\n",
    "                    st.append(matrix[i][j])\n",
    "                else:\n",
    "                    ret += matrix[i][j]\n",
    "                    mn = min(mn, matrix[i][j])\n",
    "        st.sort()\n",
    "        if len(st) & 1:\n",
    "            if len(st) < n ** 2 and st[-1] + mn < 0:\n",
    "                return ret - sum(st) - 2 * mn\n",
    "            return ret - sum(st[:-1]) + st[-1]\n",
    "        else:\n",
    "            return ret - sum(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        \n",
    "        n = len(matrix)\n",
    "        nums = []\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                nums.append(matrix[i][j])\n",
    "        nums.sort()\n",
    "        neg = sum(x<0 for x in nums)\n",
    "        s = sum(abs(x) for x in nums)\n",
    "        zero = nums.count(0)\n",
    "        if neg%2 == 0 or zero:\n",
    "            return s\n",
    "       \n",
    "        return s - min(abs(x) for x in nums)*2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        s = sum(sum(row) for row in matrix)\n",
    "        neg = [x for row in matrix for x in row if x <= 0]\n",
    "        if len(neg) % 2 == 0:\n",
    "            return s - sum(neg) * 2\n",
    "        return s - sum(neg) * 2 - min([abs(x) for row in matrix for x in row]) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 8 directions\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        st = []\n",
    "        n = len(matrix)\n",
    "        ret, mn = 0, inf\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] < 0:\n",
    "                    st.append(matrix[i][j])\n",
    "                else:\n",
    "                    ret += matrix[i][j]\n",
    "                    mn = min(mn, matrix[i][j])\n",
    "        st.sort()\n",
    "        if len(st) & 1:\n",
    "            if len(st) < n ** 2 and st[-1] + mn < 0:\n",
    "                return ret - sum(st) - 2 * mn\n",
    "            return ret - sum(st[:-1]) + st[-1]\n",
    "        else:\n",
    "            return ret - sum(st)\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        s = sum(sum(row) for row in matrix)\n",
    "        neg = [x for row in matrix for x in row if x <= 0]\n",
    "        if len(neg) % 2 == 0:\n",
    "            return s - sum(neg) * 2\n",
    "        return s - sum(neg) * 2 - min([abs(x) for row in matrix for x in row]) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\r\n",
    "        cnt = 0\r\n",
    "        m = len(matrix)\r\n",
    "        n = len(matrix[0])\r\n",
    "        min_abs = float('inf')\r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                if matrix[i][j]<0:\r\n",
    "                    cnt += 1\r\n",
    "                min_abs = min(min_abs, abs(matrix[i][j]))\r\n",
    "        if cnt % 2 == 0:\r\n",
    "            # 偶数个负数\r\n",
    "            return sum([abs(x) for row in matrix for x in row])\r\n",
    "        else:\r\n",
    "            # 奇数个负数,找到最小的负数\r\n",
    "            return sum([abs(x) for row in matrix for x in row]) - 2 * min_abs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        h, w = len(matrix), len(matrix[0])\n",
    "        pos = []\n",
    "        neg = [] \n",
    "        zero = 0 \n",
    "        for i in range(h):\n",
    "            for j in range(w):\n",
    "                x = matrix[i][j]\n",
    "                if x>0:\n",
    "                    pos.append(x)\n",
    "                elif x<0:\n",
    "                    neg.append(-x)\n",
    "                else:\n",
    "                    zero += 1 \n",
    "        pos.sort()\n",
    "        neg.sort()\n",
    "        # print(pos,neg,zero)\n",
    "        rv = sum(pos) \n",
    "        while len(neg)>1:\n",
    "            rv += neg.pop() + neg.pop()  \n",
    "        if len(neg) == 1:\n",
    "            if zero>0:\n",
    "                rv += neg[0]\n",
    "            elif len(pos)>0 and pos[0]<neg[0]:\n",
    "                rv += neg[0] - 2*pos[0]\n",
    "            else:\n",
    "                rv -= neg[0]\n",
    "        return rv "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        A=[]\n",
    "        c=0\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                x=matrix[i][j]\n",
    "                if x<0:\n",
    "                    c+=1\n",
    "                A.append(abs(x))\n",
    "        A.sort()\n",
    "        if c&1:\n",
    "            return sum(A[1:])-A[0]\n",
    "        else:\n",
    "            return sum(A)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        matrix = list(reduce(lambda l1, l2: l1 + l2, matrix))\n",
    "        negative = sum(map(lambda n: n < 0, matrix))\n",
    "        abs_sum = sum(map(lambda n: abs(n), matrix))\n",
    "        largest_negative = min(map(lambda n: abs(n), matrix))\n",
    "        return abs_sum - largest_negative * 2 * (negative % 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import reduce\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n",
    "        # 二维降一维，便于操作\n",
    "        matrix = list(reduce(lambda l1, l2: l1 + l2, matrix))\n",
    "        # 统计数组中负数个数\n",
    "        negative = sum(map(lambda n: n < 0, matrix))\n",
    "        # 统计数组中所有元素的绝对值之和\n",
    "        abs_sum = sum(map(lambda n: abs(n), matrix))\n",
    "        # 统计数组中最大（最靠近零）的负数的绝对值\n",
    "        largest_negative = min(map(lambda n: abs(n), matrix))\n",
    "        # 如果负数个数为偶数，则可以将所有数字翻转为整数，否则必须留一个负数，留绝对值最小的那个\n",
    "        #print(abs_sum, negative, largest_negative)\n",
    "        return abs_sum - largest_negative * 2 * (negative % 2)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
